package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LetterCombinationsOfAPhoneNumber{
    public static void main(String[] args) {
         
         Solution solution = new LetterCombinationsOfAPhoneNumber().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return Collections.emptyList();
        String[] mappings = new String[10];
        mappings[2] = "abc";
        mappings[3] = "def";
        mappings[4] = "ghi";
        mappings[5] = "jkl";
        mappings[6] = "mno";
        mappings[7] = "pqrs";
        mappings[8] = "tuv";
        mappings[9] = "wxyz";
        char[] path = new char[digits.length()];
        backTrack(mappings,digits,0,path);
        return result;
    }

        private void backTrack(String[] mappings, String digits, int k, char[] path) {
            if (k == digits.length()){
                result.add(new String(path));
                return;
            }

            String mapping = mappings[digits.charAt(k) - '0'];
            for (int i = 0; i < mapping.length(); i++) {
                path[k] = mapping.charAt(i);
                backTrack(mappings,digits,k+1,path);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}